import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class TextDemo {
    public static void radixSort(int[] arr) {
        if (arr == null) return;
        // 找出最大值
        int max = 0;
        for (int value : arr) {
            if (value > max) {
                max = value;
            }
        }
        // 计算最大数字的长度
        int maxDigitLength = 0;
        while (max != 0) {
            maxDigitLength++;
            max /= 10;
        }
        // 使用计数排序算法对基数进行排序
        int[] counting = new int[10];
        int[] result = new int[arr.length];
        int dev = 1;
        for (int i = 0; i < maxDigitLength; i++) {
            for (int value : arr) {
                int radix = value / dev % 10;
                counting[radix]++;
            }
            for (int j = 1; j < counting.length; j++) {
                //看见该元素的下标（arr）的某一种元素的第一下标
                counting[j] += counting[j - 1];
            }
            // 使用倒序遍历的方式完成计数排序
            for (int j = arr.length - 1; j >= 0; j--) {
                int radix = arr[j] / dev % 10;
                //看看每个数的下标
                result[--counting[radix]] = arr[j];
                //应为是前置的所以前面的不用counting[0]--;


            }
            // 计数排序完成后，将结果拷贝回 arr 数组
            System.arraycopy(result, 0, arr, 0, arr.length);
            // 将计数数组重置为 0
            Arrays.fill(counting, 0);
            dev *= 10;
        }
    }


    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<arr1.length;i++){
            if(min>arr1[i]) min = arr1[i];
            if(max<arr1[i]) max = arr1[i];
        }
        int range = max-min+1;
        int[] counting = new int[range];
        for(int element : arr1){
            counting[element-min]++;
        }
        int index = 0;
        int[] ans = new int[arr1.length];
        for(int element : arr2){
            while(counting[element-min]!=0){
                ans[index++] = element;
                counting[element-min]--;
            }
        }
        for(int x = 0;x<counting.length;x++){
            while(counting[x]!=0){
                ans[index++] = x+min;
                counting[x]--;
            }
        }
        return ans;
    }



    private static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = new int[]{2,1,4,3,9,6};

    }

    public static void countSort(int[] array){
        if(array==null||array.length<=1){
            return ;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<array.length;i++){
            if(array[i]>max) max = array[i];
            if(array[i]<min) min = array[i];
        }
        int range = max-min+1;
        int[] counting = new int[range];
        for(int element : array){
            counting[element-min]++;
        }
        counting[0]--;
        for(int i = 1;i<range;i++){
            counting[i]+=counting[i-1];
        }
        int[] result = new int[array.length];
        for(int i = array.length-1;i>=0;i--){
            result[counting[array[i]-min]] = array[i];
            counting[array[i]-min]--;
        }


    }
    public static void countSortT(int[] array){
        if(array==null|| array.length<=1){
            return ;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<array.length;i++){
            if(array[i]>max){
                max = array[i];
            }
            if(array[i]<min){
                min = array[i];
            }
        }
        int range = max-min+1;
        int[] counting = new int[range];
        for(int element:array){
            counting[element-min]++;
        }
        int prevCount = 0;

        for(int i = 0;i<range;i++){
            prevCount+=counting[i];
            counting[i] = prevCount-counting[i];
        }
        int[] result = new int[array.length];
        for(int element : counting){
            result[counting[element-min]] = element;
            counting[element-min]++;
        }
        for(int i =0;i<array.length;i++){
            array[i] = result[i];
        }
    }
    public static void countSort0_9(int[] array){
        int[] counting = new int[9];
        //7, 8, 9, 7, 6, 7, 6, 8, 6, 6
        //在这里countint是存储array里面元素对应countint下标
        //counting 存储的元素代表0~9分别在array里面存储了几次
        for(int element:array){
            counting[element-1]++;
        }
        // 0 0 0 0 0 4 3 2 1
        int preCounts = 0;
        for(int i = 0;i<counting.length;i++){
            int tem = counting[i];
            counting[i] = preCounts;
            preCounts+=tem;
        }
        //在这里counting 下标代表array里面对应的元素
        //counting的元素代表在对应的下标（array里面的元素）比该元素小的
        //0 0 0 0 0 4 7 9 10
    int[] result = new int[array.length];
        for(int element:array){
            //index代表的是这个元素应该出现的位置
            int index = counting[element-1];
            result[index] = element;
            //这里++代表以后这个位置的
            counting[element-1]++;

        }
        for(int i = 0;i<array.length;i++){
            array[i] = result[i];
        }
    }
    public static void countSort9(int[] array){
        int[] count = new int[9];
        HashMap<Integer, Queue<Integer>> map = new HashMap<>();
        for(int element:array){
            count[element-1]++;
            if(!map.containsKey(element-1)){
                map.put(element,new LinkedList<>());
            }
            map.get(element-1).add(element);
        }
        int index = 0;
        for(int i =0;i<9;i++){
            while(count[i]!=0){
                array[index++] = map.get(i).remove();
                count[i]--;
            }
        }
    }

    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {

            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}
